/*
    10个楼梯
    一次可以爬一个，也可以爬两个


*/

//第10次,有两个方式到达
//1.8级能到
//2.9级 爬一个
//递归函数1
const climbStairs = function(n){
    if(n<2){
        return n
    }else{
        return climbStairs(n-1)+climbStairs(n-2)
    }
}
console.time('hehe')
console.log(climbStairs(10))
console.timeEnd('hehe')
//递归函数2
const fn = (n,map)=>{
    if(n<=2){
        return n
    }
    const result = map[n];
    if(result){
        return result
    }else{
        let num = fn(n-1,map)+fn(n-2,map)
        map[n]= num
        return num
    }
}
console.time('hehe1')
console.log(fn(10,{}))
console.timeEnd('hehe1')

//动态规划的解决方案
const climbStairsSport = function (n) { 
    const result = [0, 1, 2]; 
    for (let i = 3; i <= n; i += 1) { 
        result[i] = result[i - 1] + result[i - 2]; 
    } 
    return result[n]; 
}; 
console.time('hehe2')
console.log(climbStairsSport(10,{}))
console.timeEnd('hehe2')